/*
 * 扩展欧几里得
 * 模板说明
 */

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

// m * x + n * y = g
template<typename T>
T ext_gcd(T m, T n, T &x, T &y){
	if(m % n == 0){
		x = 1;
		y = 1 - m/n;
		return n;
	}else if(n % m == 0){
		x = 1 - n / m;
		y = 1;
		return m;
	}else{
		T x1, y1;
		T g = ext_gcd(n, m % n, x1, y1);
		x = y1;
		y = x1 - (m/n) * y1;
		return g;
	}
}
int main(int argc, char* argv[])
{
    return 0;
}
